package zcw.com.lib_leet_code;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/10/12.<br><br>
 *
 * 中等：恢复二叉搜索树
 */
public class Topic99 {

    public static void main(String[] args) {
        Topic99 instance = new Topic99();

        TreeNode root = Util.createTree(Arrays.asList(1, 3, null, null, 2));
        instance.recoverTree(root);
        Util.preTravelTree(root);
        Util.inTravelTree(root);
        Util.postTravelTree(root);
        Util.levelTravelTree(root);

        root = Util.createTree(Arrays.asList(3, 1, 4, null, null, 2));
        instance.recoverTree(root);
        Util.preTravelTree(root);
        Util.inTravelTree(root);
        Util.postTravelTree(root);
        Util.levelTravelTree(root);
    }

    public void recoverTree(TreeNode root) {
        TreeNode pre = null;
        TreeNode node1 = null;
        TreeNode node2 = null;

        while (root != null) {
            if(root.left != null) {
                TreeNode preTemp = root.left;
                while (preTemp.right != null && preTemp.right != root) {
                    preTemp = preTemp.right;
                }

                if(preTemp.right == null) {
                    preTemp.right = root;
                    root = root.left;
                }
                else {
                    if(pre != null && pre.val > root.val) {
                        node2 = root;
                        if(node1 == null) {
                            node1 = pre;
                        }
                    }
                    pre = root;

                    preTemp.right = null;
                    root = root.right;
                }
            }
            else {
                if(pre != null && pre.val > root.val) {
                    node2 = root;
                    if(node1 == null) {
                        node1 = pre;
                    }
                }
                pre = root;

                root = root.right;
            }
        }

        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }

    public void recoverTree4(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode pre = null;
        TreeNode node1 = null;
        TreeNode node2 = null;

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();

            if(pre != null && pre.val > root.val) {
                node2 = root;
                if(node1 == null) {
                    node1 = pre;
                }
                else {
                    break;
                }
            }
            pre = root;

            root = root.right;
        }

        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }

    public void recoverTree3(TreeNode root) {
        TreeNode[] nodeArray = new TreeNode[3];
        inTravel3(root, nodeArray);

        int temp = nodeArray[1].val;
        nodeArray[1].val = nodeArray[2].val;
        nodeArray[2].val = temp;
    }

    private void inTravel3(TreeNode root, TreeNode[] array) {
        if(root == null) {
            return ;
        }

        inTravel3(root.left, array);

        if(array[0] != null && array[0].val > root.val) {
            array[2] = root;

            if(array[1] == null) {
                array[1] = array[0];
            }
        }
        array[0] = root;

        inTravel3(root.right, array);
    }

    public void recoverTree2(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        inTravel2(root, list);
        recover2(list);
    }

    private void inTravel2(TreeNode root, List<TreeNode> list) {
        if(root == null) {
            return ;
        }

        inTravel2(root.left, list);
        list.add(root);
        inTravel2(root.right, list);
    }

    private void recover2(List<TreeNode> list) {
        int index1 = -1;
        int index2 = -1;
        for(int i = 0; i < list.size() - 1; i++) {
            if(list.get(i).val > list.get(i + 1).val) {
                index2 = i + 1;
                if(index1 == -1) {
                    index1 = i;
                }
                else {
                    break;
                }
            }
        }

        int temp = list.get(index1).val;
        list.get(index1).val = list.get(index2).val;
        list.get(index2).val = temp;
    }
}
